package ru.nsu.ccfit.shumkina.algorithm.adaptation.profitcounter;

import ru.nsu.ccfit.shumkina.algorithm.graphworks.Graph;
import ru.nsu.ccfit.shumkina.algorithm.graphworks.Page;

import java.util.ArrayList;
import java.util.Map;
import java.util.TreeMap;

/**
 * Created with IntelliJ IDEA.
 * User: vera
 * Date: 5/15/13
 * Time: 4:56 PM
 * To change this template use File | Settings | File Templates.
 */
public class UtilityFunctions {
    public static ArrayList<String> findShortestPath(String from, String to, Graph graph, int maxSize)
    {
        //if ()
        ArrayList<String> shortestPath = new ArrayList<String>();
        Page startPage = graph.pages.get(from);
        Page finalPage = graph.pages.get(to);

        if (startPage == null || finalPage == null)
            return null;

        ArrayList<String> currentPath = new ArrayList<String>();
        TreeMap<Integer, ArrayList<String>> pathsFound = new TreeMap<Integer, ArrayList<String>>();
        currentPath.add(startPage.pageId);
        if (startPage == finalPage)
            return currentPath;
        findPaths(startPage, finalPage, currentPath, pathsFound, maxSize);

        if (pathsFound.isEmpty())
            return null;
        return  pathsFound.firstEntry().getValue();
    }

    private static void findPaths(Page startPage, Page finalPage, ArrayList<String> currentPath,
                                  TreeMap<Integer, ArrayList<String>> pathsFound, int maxSize) {
        // temporary limitation
        // change 10 to bigger value if paths are longer and can't be found.
        // Note: with value 15 program starts to work notable slower,
        // with 20 it won't finish at least in time limit of 5 minutes
        // in my tests replaced paths wasn't longer than 5 pages, actually
        if (currentPath.size() > maxSize)
            return;
        if (!pathsFound.isEmpty() && currentPath.size() > pathsFound.firstEntry().getValue().size())
            return;
        if (startPage.children.containsKey(finalPage.pageId))
        {
            //path found
            ArrayList<String> path = new ArrayList<String>(currentPath);
            path.add(finalPage.pageId);
            pathsFound.put(path.size(), path);
            return;
        }

        for (Map.Entry<String, Page> entry: startPage.children.entrySet())
        {
            // no cycles!
            if (currentPath.contains(entry.getKey()))
                continue;

            currentPath.add(entry.getKey());
            findPaths(entry.getValue(), finalPage, currentPath, pathsFound, maxSize);
            currentPath.remove(currentPath.size() - 1);
        }
    }
}
